#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    vector<string> res;
    string path;
    void dfs(string s, int pos)
    {
        if (pos == s.size())
        {
            res.push_back(path);
            return;
        }

        path.push_back(s[pos]);
        dfs(s, pos + 1);
        path.pop_back();

        char ch = s[pos];
        if (ch < '0' || ch>'9')
        {
            char tmp = change(ch);
            path.push_back(tmp);
            dfs(s, pos + 1);
            path.pop_back();
        }
    }

    char change(char c)
    {
        if (c >= 'a' && c <= 'z') c -= 32;
        else c += 32;
        return c;
    }

    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return res;
    }

    bool check[16];
    int ret;
    void dfs(int n, int pos)
    {
        if (pos == n + 1)
        {
            ++ret;
            return;
        }
        for (int i = 1; i <= n; ++i)
        {
            if (!check[i] && (i % pos == 0 || pos % i == 0))
            {
                check[i] = true;
                dfs(n, pos + 1);
                check[i] = false;
            }
        }
    }

    int countArrangement(int n) {
        dfs(n, 1);
        return ret;
    }

    double myPow(double x, int n)
    {
        if (n < 0) return 1 / Pow(x, -(long long)n);
        else return Pow(x, n);
    }
    double Pow(double x, int n)
    {
        if (n == 0) return 1;
        double tmp = Pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
};